package com.acwing.partition46;

import java.io.*;
import java.util.Arrays;

/**
 * @author rkc
 * @date 2022/7/22 10:31
 */
public class AC4519正方形数组的数目 {

    private static final int N = 14;
    private static int[] w = new int[N], temp = new int[N];
    private static boolean[] st = new boolean[N];
    private static int n, ans = 0, size = 0;

    private static StreamTokenizer tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = nextInt();
        for (int i = 0; i < n; i++) w[i] = nextInt();
        Arrays.sort(w, 0, n);
        dfs();
        writer.println(ans);
        writer.flush();
    }

    private static void dfs() {
        if (size == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if ((i > 0 && w[i] == w[i - 1] && st[i - 1]) || st[i]) continue;
            temp[size++] = w[i];
            st[i] = true;
            if (size == 1 || (check(temp, 0, size - 1))) dfs();
            size--;
            st[i] = false;
        }
    }

    private static boolean check(int[] w, int l, int r) {
        boolean flag = true;
        for (int i = l; i < r; i++) {
            int t = (int) Math.sqrt(w[i] + w[i + 1]);
            if ((long) t * t != w[i] + w[i + 1]) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    private static int nextInt() throws IOException {
        tokenizer.nextToken();
        return (int) tokenizer.nval;
    }
}
